package summer.graph;

import java.util.*;

public class Solution433 {
    public static void main(String[] args) {
        String startGene = "AACCGGTT";
        String endGene = "AAACGGTA";
        String[] bank = new String[]{"AACCGGTA", "AACCGCTA", "AAACGGTA"};
        int i = minMutation(startGene, endGene, bank);
        System.out.println(i);
    }

    public static int minMutation(String startGene, String endGene, String[] bank) {
        LinkedList<String> queue = new LinkedList<>();
        queue.add(startGene);
        int res = 0;
        boolean[] used = new boolean[bank.length];
        Arrays.fill(used, false);
        while (!queue.isEmpty()) {
            int size = queue.size();
            res++;
            while (size-- > 0) {
                String curStr = queue.removeFirst();
                for (int i = 0; i < bank.length; i++) {
                    if (!isTrue(curStr, bank[i]) || used[i]) continue;
                    if (bank[i].equals(endGene)) return res;
                    used[i] = true;
                    queue.add(bank[i]);
                }
            }
        }
        return -1;
    }

    public static boolean isTrue(String s, String e) {
        int dif = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != e.charAt(i)) dif++;
        }
        return dif == 1;
    }
}
